package a16_test;

/**
 * @Author quan
 * @Description 判断是否为子字符串
 * 输入：s = "abc", t = "ahbgdc"
 * 输出：true
 * @Date 2023/4/16 21:42
 */
public class subString {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param S string字符串
     * @param T string字符串
     * @return bool布尔型
     */
    // S = "hello",T = "ell"
    public static void main(String[] args) {
        String T = "aaabcd";
        String S = "bcd";
        System.out.println(isSubsequence(S,T));
    }
    public static boolean isSubsequence (String S, String T) {
        // write code hereint
        /**
         * 失败版本：自己写的，思路也没理清楚
         */
        /*for (int i = 0; i < S.length(); i++) {
            char s = S.charAt(i);
            for (int j = 0; j < T.length(); j++) {
                char t = T.charAt(j);
                if(s==t){
                    String newS = S.substring(i);
                    for (int k = 0; k < newS.length();k++) {
                        if(t!=newS.charAt(k)){
                            return false;
                        }
                    }
                }
            }
        }
        return true;*/

        /**
         * 参考答案：双指针法
         */
        for (int i = 0, j = 0; j < T.length(); j++) {
            //边界条件
            if(S.length() == 0){
                return true;
            }
            if(S.charAt(i) == T.charAt(j)){
                //如果i已经是S的尾部，则说明S是T的子序列
                if(S.length() == ++i){
                    return true;
                }
            }
        }
        //不是子序列返回false
        return false;
    }
}
